#include <iostream>
#include <string>
using namespace std;

typedef int listType;


typedef struct listNode
{
        listType val;
        struct listNode *next;
}listNode, *plistNode;

//创建节点
plistNode list_create(listType val)
{
        plistNode newnode = new listNode;
        newnode->val = val;
        newnode->next = NULL;
        return newnode;
}

//初始化
plistNode list_init()
{
        plistNode phead = list_create(0);
        return phead;
}

//找尾
int seek_back(plistNode phead)
{
        int count = -1;
        plistNode cur = phead;
        while (cur)
        {
                count++;
                cur = cur->next;
        }
        return count;
}
//是否有元素
int empty(plistNode phead)
{
        if (phead->next == NULL)
        {
                cout << "链表无元素" << endl;
                return 1;
        }
        return 0;
}
//指定位置插入 pos从0开始
void list_insert(plistNode phead, listType val, int pos)
{
        int count = -1;
        plistNode newlist = list_create(val);
        plistNode cur = phead;
        while (cur)
        {
                count++;
                if (count == pos)
                        break;
                cur = cur->next;
        }
        if (cur == NULL)
        {
                cout << "你输入的pos过大" << endl;
        }
        newlist->next = cur->next;
        cur->next = newlist;
}
//头插
void push_front(plistNode phead, listType val)
{
        list_insert(phead, val, 0);
}
//尾插
void push_back(plistNode phead, listType val)
{
        int count = seek_back(phead);
        list_insert(phead, val, count);
}
//指定位置删除
void list_pop(plistNode phead, int pos)
{
        if (empty(phead))
                return;
        int count = -1;
        plistNode cur = phead;
        plistNode curprev = NULL;
        while (cur)
        {
                curprev = cur;
                count++;
                cur = cur->next;
                if (count == pos)
                        break;
        }
        if (cur == NULL)
        {
                cout << "你输入的pos过大" << endl;
        }
        curprev->next = cur->next;
        delete cur;
}
//头删
void pop_front(plistNode phead)
{
        list_pop(phead, 0);
}
//尾删
void pop_back(plistNode phead)
{
        int count = seek_back(phead);
        list_pop(phead, count);
}
//打印
void list_printf(plistNode phead)
{
        if (empty(phead))
                return;
        plistNode cur = phead->next;
        while (cur)
        {
                cout << cur->val << "->";
                cur = cur->next;
        }
        cout << "NULL" << endl;
}
void list_merge(plistNode p1, plistNode p2)
{

	plistNode p1end = p1;
        while (p1end->next)
        {
                p1end = p1end->next;
        }
        //找p1的尾巴
        //找到p1尾部
        plistNode curp2 = p2->next;
        while (curp2)
        {
               
                plistNode curp1 = p1->next;
                int flag = 1;
                while (curp1 != p1end)
                {
                        if (curp1->val == curp2->val)
                                flag = 0;
                        curp1 = curp1->next;
                }
                if (curp1->val == curp2->val)
                        flag = 0;
                if (flag)
                        push_back(p1,curp2->val);
                curp2 = curp2->next;
        }
}



int main()
{
        plistNode S1 = list_init();
        plistNode S2 = list_init();
        push_back(S1, 12);
        push_back(S1, 45);
        push_back(S1, 4);
        push_back(S1, 89);
        push_back(S1, 13);
        push_back(S2, 1);
        push_back(S2, 12);
        push_back(S2, 45);
        push_back(S2, 4);
        push_back(S2, 89);
        push_back(S2, 1);
        push_back(S2, 12);
        push_back(S2, 45);
        push_back(S2, 4);
        push_back(S2, 89);
        push_back(S2, 13);
        push_back(S2, 7);
        push_back(S2, 96);
        push_back(S2, 78);
        push_back(S2, 53);
        list_printf(S1);
        list_printf(S2);
        list_merge(S1, S2);
        list_printf(S1);


        return 0;
